from collections import deque
from typing import List


class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        people = deque()
        ans = []
        for height in reversed(heights):
            num = 0  # 当前小黄人能够看到的数量

            # 统计比当前小黄人更矮的数量
            while people and people[0] < height:
                num += 1
                people.popleft()

            # 如果前面还有比小黄人更高的人则可以多看到一个
            if people:
                num += 1

            people.appendleft(height)

            ans.append(num)

        return ans[::-1]


if __name__ == "__main__":
    print(Solution().canSeePersonsCount(heights=[10, 6, 8, 5, 11, 9]))  # [3,1,2,1,1,0]
    print(Solution().canSeePersonsCount(heights=[5, 1, 2, 3, 10]))  # [4,1,1,1,0]
